package com.xjl.everyinterview.datastructureandalgorithm.algorithm.sort.fast;

/**
 * @author xjl
 * @version 1.0
 * @description: 快速排序分析    --分治的思想
 *
 * @date 2021/8/19 17:06
 */
public class FastSort {

    public static void main(String[] args) {
        int[] array = new int[] {8,4,6,5,4,3,2,1};;
        quickSort(array, 0, array.length - 1);
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i]);
        }
    }

    private static void quickSort(int[] array, int start, int end) {
        if (start >= end) {
            return;
        }
        int key = array[start];
        int left = start;
        int right = end;
        boolean direction = true;
        L1:
        while (left < right) {
            if (direction) {
                for (int i = right; i > left; i--) {
                    if (array[i] < key) {
                        array[left++] = array[i];
                        right = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                right = left;
            } else {
                for (int i = left; i < right; i++) {
                    if (array[i] > key) {
                        array[right--] = array[i];
                        left = i;
                        direction = !direction;
                        continue L1;
                    }
                }
                left = right;
            }
        }
        array[left] = key;
        quickSort(array, start, left - 1);
        quickSort(array, left + 1, end);

    }
}
